#include <iostream>
#include <vector>

template<class T>
class PriorityQueueInterface
{
public:
    virtual ~PriorityQueueInterface(){}
    virtual int size()const = 0;
    virtual bool empty()const = 0;
    virtual void push(T&) = 0;
    virtual T top()const = 0;
    virtual void pop() = 0;
};


template <class T>
class PriorityQueue : public PriorityQueueInterface<T>
{
public:
    PriorityQueue(int n){
        m_max_size = n;
        m_data = new T[n + 1](); // 分配空间并初始化
        m_size = 0;
    }
    virtual ~PriorityQueue(){delete [] m_data;}

    int size()const{return m_size;}

    bool empty()const{return m_size == 0;}

    void push(T& value){
        if(m_size == m_max_size) throw "no memory.";

        // Step 1: 先将元素放在最后面
        m_data[++m_size] = value;

        // Step 2: 从当前元素到根进行一次冒泡
        int current_idx = m_size;
        while(current_idx >1){
            if(m_data[current_idx] > m_data[current_idx/2]){
                T tmp = m_data[current_idx];
                m_data[current_idx] = m_data[current_idx/2];
                m_data[current_idx/2] = tmp;
                current_idx = current_idx/2;
            }else{
                break;
            }
        }
    }

    T top()const{return m_data[1];}

    void pop(){
        if(empty()) throw "no element in queue, cannot pop.";

        // Step 1: 把最后一个元素取出来并删除当前节点。
        int last_element = m_data[m_size];
        m_data[m_size--] = 0;

        // Step 2: 从根节点开始，选择较大的子树移动到父节点。
        int current_idx = 1;
        int child = 2;
        while(child <= m_size){
            // 判断左树和右树的比较
            if(child < m_size && m_data[child] < m_data[child + 1]){
                child ++;
            }

            // 判断是否插入当前位置
            if(last_element >= m_data[child])
                break;

            // 移动下一层
            m_data[current_idx] = m_data[child];
            current_idx = child;
            child *= 2;
        }

        m_data[current_idx] = last_element;
    }

    void output(std::ostream& os){
        for(int i = 1; i <= m_size; ++i){
            os<<m_data[i]<<" ";
        }
        os<<std::endl;
    }

private:
    T* m_data;
    int m_size;
    int m_max_size;
};

int main(int argc, char *argv[])
{
  int n = 10;
  PriorityQueue<int> queue(n);

  int src[] = {20, 12, 35, 15, 10, 80, 30, 17, 2 ,1};

  for(int i =0;i < n; ++i){
    queue.push(src[i]);
  }
  queue.output(std::cout);
  for(int i = 0; i < n; ++i){
    std::cout<< queue.top()<<" ";
    queue.pop();
  }


  return 0;
}
